package pro.softzhang.algo.lc800;

import pro.softzhang.algo.flag.book.BOfferS;
import pro.softzhang.algo.flag.difficulty.DRed;
import pro.softzhang.algo.flag.knowledge.KDynamicPlanning;
import pro.softzhang.algo.flag.theme.TMathFibonacci;

import java.util.HashMap;
import java.util.Map;

@KDynamicPlanning
@DRed
@TMathFibonacci
@BOfferS
public class LC873_LengthOfLongestFibonacciSubsequence {
    public static void main(String[] args) {

    }

    /**
     *
     */
    static
    class Solution {
        public int lenLongestFibSubseq(int[] arr) {
            Map<Integer, Integer> m = new HashMap<>();
            for (int i = 0; i < arr.length; i++) {
                m.put(arr[i], i);
            }

            int[][] dp = new int[arr.length][arr.length];
            int r = 2;
            for (int i = 1; i < arr.length; i++) {
                for (int j = 0; j < i; j++) {
                    int k = m.getOrDefault(arr[i] - arr[j], -1);
                    dp[i][j] = k >= 0 && k < j ? dp[j][k] + 1 : 2;
                    r = Math.max(r, dp[i][j]);
                }
            }
            return r > 2 ? r : 0;
        }
    }
}
